#include <iostream> 
#include <vector>
#include <set>
#include <string>
// 定义节点(Node)的结构体
using namespace std;

struct Node {
    int id; // 节点的唯一标识符
    int switch_count; // 节点的切换计数

    // 构造函数
    Node(int nodeId, int switchCount) : id(nodeId), switch_count(switchCount) {}
};

// 定义边(Edge)的结构体
struct Edge {
    int id; // 边的唯一标识符
    int node1Id; // 边的一个端点的编号
    int node2Id; // 边的另一个端点的编号
    bool channel[40]; // 边的信道标识

    // 构造函数
    Edge() {}

    Edge(int edgeId, int n1Id, int n2Id) : id(edgeId), node1Id(n1Id), node2Id(n2Id) {
        // 初始化所有信道为未被占用
        for(int i = 0; i < 40; i++) {
            channel[i] = false;
        }
    }
};
/*struct Path{
    Node now;
    Path* next;
    Path(int nowId, int nowCount, Path* _next = nullptr) : now(nowId,nowCount), next(_next) {}
};*/
struct Transaction{
    std::vector<Edge> path;
    // 起点
    int start;
    //终点
    int end;
    //边的数目
    int count;
    //业务价值
    int value;
    //所占通道范围 左边
    int l;
    //右边界
    int r;
    //Path* paths;
    Transaction(int _start, int _end, int _count, int _l, int _r, int _value)
        : start(_start), end(_end), count(_count), l(_l), r(_r), value(_value){
    }
};
// 定义图(Graph)的结构体，用于存储图的所有节点和边
struct Graph {
    std::vector<Node> nodes; // 存储图中所有节点
    std::vector<Edge> edges; // 存储图中所有边
    std::vector<Transaction> transactions; // 存储图中的所有业务
    int parent[205]; // 并查集的父节点数组

    // 向图中添加节点
    void addNode(const Node& node) {
        nodes.push_back(node);
        parent[node.id] = node.id;
    }

    // 通过节点编号查找节点的引用
    Node* findNodeById(int id) {
        for (Node& node : nodes) {
            if (node.id == id) {
                return &node;
            }
        }
        return nullptr; // 如果找不到返回nullptr
    }

    // 向图中添加边，通过节点编号
    void addEdgeById(int edgeId, int node1Id, int node2Id) {
        Node* node1 = findNodeById(node1Id);
        Node* node2 = findNodeById(node2Id);
        if(node1Id == node2Id) {
            std::cout << "Cyclic Path\n";
            return;
        }
        if (node1 && node2) { // 确保两个节点都找到了
            edges.emplace_back(edgeId, node1Id, node2Id); // 使用构造函数初始化Edge对象
            unionSets(node1Id, node2Id);
        } else {
            std::cout << "Error: Node not found.\n";
        }
    }
    // 向图中添加业务
    void addTransaction(int start, int end, int count, int l, int r, int value) {
        Transaction newTransaction(start, end, count, l, r, value);
        std::set<int> usedNodeId;
        std::set<int> usedEdgeId;
        int e = start;//用于存储路径的尾巴节点编号
        usedNodeId.insert(start);//起点加入

        for(int j = 0; j < count; j++){
            int edgecount=0;//对输入边数进行计数
            int edgeId;
            cin >> edgeId;
            edgecount++;  
            // 检查 edgeId 是否重复
            if (usedEdgeId.find(edgeId) != usedEdgeId.end()) {
              // 如果 edgeId 已经存在于 usedEdgeIds 中，说明重复
              cout << "Duplicate Edge ID." << endl;
              break;
            }

            usedEdgeId.insert(edgeId); // 插入新的ID到集合中，表示已经使用

            bool found = false;
            for (const Edge& edge : edges) {
              if (edge.id == edgeId) {
                 if(edge.node1Id != e && edge.node2Id != e){
                    // 如果这条边的两个节点都不是尾部节点e，则说明不连通
                    cout << "Disconnected Path." << endl;
                    break;
                 }
                 int nonEId = (edge.node1Id == e) ? edge.node2Id : edge.node1Id; // 找到不是尾部的另一个节点
                 if (usedNodeId.find(nonEId) != usedNodeId.end()) {
                    // 如果nonEId节点已经存在于usedNodeId中，则发现了环路
                    cout << "Cyclic Path." << endl;
                    break;
                 }

                // 将非尾部节点加入usedNodeId，并更新尾部节点为边的另一节点
                usedNodeId.insert(nonEId);
                e = (edge.node1Id == e) ? edge.node2Id : edge.node1Id; // 更新尾部节点为边的另一节点

                newTransaction.path.push_back(edge);
                found = true;
                break; // 找到对应边后退出循环
              }
            }

            if (!found) {
              cout << "Incorrect Edge ID." << endl;
            }
        }
        transactions.push_back(newTransaction);
    }
    // 查找带路径压缩的根节点
    int find(int nodeId) {
        // printf("%d\n", nodeId);
        if (parent[nodeId] != nodeId) {
            parent[nodeId] = find(parent[nodeId]); // 路径压缩
        }
        return parent[nodeId];
    }

    // 合并两个集合
    void unionSets(int node1Id, int node2Id) {
        int root1 = find(node1Id);
        int root2 = find(node2Id);
        if (root1 != root2) {
            // 后续可以使用树来优化
            parent[root2] = root1; // 将root2的根指向root1
        }
    }

    // 判断两个节点是否连通
    bool isConnected() {
        int firstRoot = find(1); // 假设第一个节点为起点找根节点
        for(int i = 1; i <=nodes.size(); ++i) {
            if(firstRoot != find(i)) return false; // 如果有节点的根节点和第一个不一样，则不连通
        }
        printf("true");
        return true; // 所有节点根节点一样，即连通
    }
    void printEdges() const {
        for (const Edge& edge : edges) {
            std::cout << "Edge ID: " << edge.id << " connects Node " << edge.node1Id;
            std::cout << " and Node " << edge.node2Id << std::endl;
        }
    }
    // 打印图中所有节点的id和switch_count的方法
    void printNodes() const {
        for (const Node& node : nodes) {
            std::cout << "Node ID: " << node.id << ", Switch Count: " << node.switch_count << std::endl;
        }
    }
    // 打印业务和路径的方法
    void printTransactions() const {
        for (const Transaction& transaction : transactions) {
        // 打印业务的基本信息
        std::cout << "Transaction from " << transaction.start << " to " << transaction.end<<endl;
        std::cout << "The number of edges passed by the transaction is "<<transaction.count<<endl;
        std::cout << "value: " << transaction.value << ", channel range [" << transaction.l << ", " << transaction.r << "]\n";
        std::cout << "  Path includes " << transaction.path.size() << " edges:\n";
        
        // 遍历并打印路径中的所有边
        for (const Edge& edge : transaction.path) {
            std::cout << "    Edge ID: " << edge.id<<endl;
        }
    }
    }
};


int main() {
    // 创建图的实例
    Graph myGraph;
    int nodeCount;
    int edgeCount;
    int transCount;
    std::cout << "Enter the number of nodes: ";
    std::cin >> nodeCount;
    std::cout << "Enter the number of edges: ";
    std::cin >> edgeCount;
    
    for(int i=1; i<=nodeCount; i++){
        int switch_count;
        std::cin>> switch_count;
        myGraph.addNode(Node(i, switch_count));
    }
    for(int i=1; i<=edgeCount; i++){
        int node1;
        int node2;
        std::cin>> node1;
        std::cin>> node2;
        myGraph.addEdgeById(i, node1, node2);
    }
    // 使用节点编号添加边到图中
    myGraph.printNodes();
    myGraph.printEdges();
    if (!myGraph.isConnected()) {
        std::cout << "Disconnected Path.\n";
        // exit(0);
    } 
    cin>>transCount;
    for(int i=0;i<transCount;i++){
        int src,snk,s,l,r,v;
        cin>>src>>snk>>s>>l>>r>>v;
        myGraph.addTransaction(src,snk,s,l,r,v);
    }
    myGraph.printTransactions();
    return 0;
}